//
//  BC_Zoo.m
//  CocOth
//
//  Created by BrunoCausse on 17/12/10.
//  Copyright 2010-2013 poulailler cie. All rights reserved.
//

#include <unistd.h>

#import "BC_Zoo.h"

#import "CocOthAppController.h"

#import "BC_ZooRequest.h"
#import "BC_SplitPoint.h"

#import "BC_Const.h"
#import "BC_Board.h"
#import "BC_Move.h"
#import "BC_Utils.h"

#import "BC_Hashtable.h"
#import "BC_Hashvalue.h"


#define MAX_THREADS 500

//Methodes privées
@interface BC_Zoo(PrivateAPI) 

- (void)open;
- (void)close;
- (void)reconnect:(NSTimer *)theTimer;

- (void)initOptions;
- (void)changeOptions;

- (void)keepAlive:(NSTimer *)theTimer;
- (void)newTest;

- (void)send:(NSString *)aString;
- (void)process:(NSString *)aString;


- (void)stopRequest:(BC_ZooRequest *)aRequest;

- (void)solver:(NSURL *)input;
- (void)myMainThread:(BC_Board *)aBoard;

- (BC_ZooRequest *)driverPVS:(BC_Board *)board;

- (BC_ZooRequest *)PVS:(BC_Board *)board
                 alpha:(int)alpha
                  beta:(int)beta
           selectivity:(unsigned int)cut
                passed:(BOOL)passed
            splitpoint:(BC_SplitPoint *)parent;

- (void)MP_NWS:(BC_SplitPoint *)splitpoint;

//- (void)MP_PVS:(BC_SplitPoint *)splitpoint;

- (BC_ZooRequest *)evaluateWithBoard:(BC_Board *)board
                               depth:(unsigned int)aDepth
                         selectivity:(unsigned int)aCut
                               alpha:(int)lower
                                beta:(int)upper
                          splitpoint:(BC_SplitPoint *)sp;

- (BOOL)splitWithBoard:(BC_Board *)board
             listMoves:(NSMutableArray *)moves
                 alpha:(int)lower
                  beta:(int)upper
           selectivity:(unsigned int)cut
            splitpoint:(BC_SplitPoint *)sp_Parent
                result:(BC_ZooRequest *)result;


- (NSString *)mainLineWithBoard:(BC_Board *)board
                          score:(int)value;

//debug
- (BOOL)redirectNSLog;
@end


@implementation BC_Zoo

@synthesize asker;
@synthesize nRequests;



/*
 initialisation
 */
- (id)initWithAppController:(CocOthAppController *)controller
{
	self = [super init];
	if (self) {
		
		appController = controller; //simple assignation
		
		//asker aleatoire
		srandom(time(NULL));
		asker = random();
		
		requests  = [[NSMutableArray alloc] init];
		nRequests = 0;
		
		IO_sync = [[NSLock alloc] init];
		
		
		
    
		[self open];
		
//		threadMain = nil;
		
		if(DEBUG)
			[self redirectNSLog];
		
		createThreadLock = [[NSLock alloc] init];
		nThreads = 0;
    
    hashtable = [[BC_Hashtable alloc] initWithNumberOfBits:16];
    
    options = [[NSMutableDictionary alloc] initWithCapacity:16];
    
		[self initOptions];
    
    
    
	}
	
	return self;
	
}


/*
 invalide le timer
 */
- (void)invalidate
{
	if (keepAlive && [keepAlive isValid]) {
		[keepAlive invalidate];
		keepAlive = nil;
	}
}

- (void)disconnect
{
	//stop les requetes
	[self aborting];
	
	//invalide les timers
	[self invalidate];
	if (observerConnectTimer && [observerConnectTimer isValid]) {
		[observerConnectTimer invalidate];
		observerConnectTimer = nil;
	}
	
	//ferme les streams
	[self close];
	
	[appController zooWillClose];
	
}


/* 
 *****************************************************************************************
 *                                                                                       *
 * initOptions() : initialisation des valeurs par defaut de l'algo de recherche.         *
 *                                                                                       *
 *****************************************************************************************
 */
- (void)initOptions
{
  limit_leaf                              = 25;
	
  [options setObject:@"YES" forKey:@"SELECTIVITY"];
  [options setObject:@"YES" forKey:@"HORIZON_FEUILLES_EST_VARIABLE"];
  [options setObject:@"YES" forKey:@"ACCURATE_ORDERING"];
  [options setObject:@"YES"  forKey:@"CONSERVATIVE_YBWC"];
  [options setObject:@"YES"  forKey:@"SPECULATIVE_YBWC"];
  
  // on indique a l'algo de recherche ces valeurs initiales
  [self changeOptions];
}


/* 
 *****************************************************************************************
 *                                                                                       *
 * changeOptions() : apres chaque lecture d'une option dans un script, if faut appeler   *
 * cette fonction qui met à jour les valeurs des variables globales modifiant l'algo     *
 * de recherche.                                                                         *
 *                                                                                       *
 *****************************************************************************************
 */
- (void)changeOptions
{
	search_should_use_selectivity           = [[options objectForKey:@"SELECTIVITY"] isEqual:@"YES"];
	search_should_use_variable_leaf_horizon = [[options objectForKey:@"HORIZON_FEUILLES_EST_VARIABLE"] isEqual:@"YES"];
	search_should_use_accurate_ordering     = [[options objectForKey:@"ACCURATE_ORDERING"] isEqual:@"YES"];
	search_should_use_conservative_YBWC     = [[options objectForKey:@"CONSERVATIVE_YBWC"] isEqual:@"YES"];
	search_should_use_speculative_YBWC      = [[options objectForKey:@"SPECULATIVE_YBWC"] isEqual:@"YES"];
}



- (void)dealloc
{	
  
	[options release];
  
	[hashtable release];
	
	[createThreadLock release];
	
	[requests release];
	
	[IO_sync release];
	
	[super dealloc];
}

/*
 auto-reconnection
 */
- (void)reconnect:(NSTimer *)theTimer
{
	[self invalidate];
	observerConnectTimer = nil;
	[self close];
	[appController zooWillClose];
  
	
	[self open];
}


/*
 ouvre les flux
 lance les timers
 */
- (void)open
{
  //	NSLog(@"connect....");
	
	NSHost *host = [NSHost hostWithAddress:@"78.192.201.23"];
	
	[NSStream getStreamsToHost:host port:80 inputStream:&iStream outputStream:&oStream];

	[iStream retain];
	[oStream retain];
	
	[iStream setDelegate:self];
	[oStream setDelegate:self];
  
  //	[iStream scheduleInRunLoop:[NSRunLoop currentRunLoop] forMode:NSDefaultRunLoopMode];
  //	[oStream scheduleInRunLoop:[NSRunLoop currentRunLoop] forMode:NSDefaultRunLoopMode];
  
	[iStream scheduleInRunLoop:[NSRunLoop currentRunLoop] forMode:NSRunLoopCommonModes];
	[oStream scheduleInRunLoop:[NSRunLoop currentRunLoop] forMode:NSRunLoopCommonModes];
  
	[iStream open];
	[oStream open];
  
	//scheduled sur la runLoop
  //	keepAlive = [NSTimer scheduledTimerWithTimeInterval:15
  //												 target:self
  //											   selector:@selector(keepAlive:)
  //											   userInfo:nil
  //												repeats:YES];
	
  keepAlive = [NSTimer timerWithTimeInterval:15
                                      target:self
                                    selector:@selector(keepAlive:)
                                    userInfo:nil
                                     repeats:YES];  
  
  [[NSRunLoop mainRunLoop] addTimer:keepAlive forMode:NSRunLoopCommonModes];
	
	//scheduled sur la runLoop
  //	observerConnectTimer = [NSTimer scheduledTimerWithTimeInterval:20
  //															target:self
  //														  selector:@selector(reconnect:)
  //														  userInfo:nil
  //														   repeats:NO];
	
	
  
  observerConnectTimer = [NSTimer timerWithTimeInterval:20
                                                 target:self
                                               selector:@selector(reconnect:)
                                               userInfo:nil
                                                repeats:NO];  
  
  [[NSRunLoop mainRunLoop] addTimer:observerConnectTimer forMode:NSRunLoopCommonModes];
	
}

/*
 ferme les flux
 */
- (void)close
{
  //	NSLog(@"close.....");
  
	[iStream close];
	[oStream close];
  
	[iStream removeFromRunLoop:[NSRunLoop currentRunLoop] forMode:NSDefaultRunLoopMode];
	[oStream removeFromRunLoop:[NSRunLoop currentRunLoop] forMode:NSDefaultRunLoopMode];
  
	[iStream release];
	[oStream release];
	
	iStream = nil;
	oStream = nil;
	
	iStreamCompletedOpen = NO;
	oStreamCompletedOpen = NO;
	
}

/*
 requete KEEP_ALIVE
 */
- (void)keepAlive:(NSTimer *)theTimer
{
	[IO_sync lock];
	[self send:[NSString stringWithFormat:@"KEEP_ALIVE&asker=%ld&status=IDLE", asker]];
	[IO_sync unlock];
  
}


/*
 *****************************************************************************************
 *                                                                                       *
 * newTest() : cette fonction est appelée lors de la lecture d'un script pour remettre   *
 * à zero l'état de recherche de CocOth, du zoo et de tous ses calculateurs, afin que    *
 * l'on puisse faire des comparaisons de temps les plus équitables possibles. Il faut    *
 * essayer de vider *tous* les caches, les tables de hachage, etc. auxquels on pense.    *
 *                                                                                       *
 *****************************************************************************************
 */
- (void)newTest
{
    NSLog(@"--");
    NSLog(@"=========================================================================================");
	NSLog(@"Sending START_NEW_TEST to the zoo...");
	NSLog(@"--");
	
	// broadcast the commande START NEW TEST to all the calculators : they
	// should reset their internal state...
	[IO_sync lock];
	[self send:@"START_NEW_TEST"];
	[IO_sync unlock];
	
	// empty the hash tables in CocCoth : the cleanest way is to dispose and reallocate the memory
	[hashtable release];
	hashtable = [[BC_Hashtable alloc] initWithNumberOfBits:16];
	
	// sleep for 4 seconds : this gives enough time to Cassio to restart the engines.
	sleep(4);     
	
}


/*
 STOP la requete
 */

- (void)stopRequest:(BC_ZooRequest *)aRequest
{
	[IO_sync lock];
	
	if([aRequest state] == STOP) {
		
		//potentiel bug
		//il faut laisser la requete vivante si il existe une transposition.
		unsigned int nSameHash = 0;
		unsigned long long hash = [aRequest hash];
		for(int iRequest = nRequests -1; iRequest >=0; iRequest--) {
			
			BC_ZooRequest *request = [requests objectAtIndex:iRequest];
			
			if([request hash] == hash) {
				
				nSameHash++;
				
				if (request == aRequest) { //meme objet -> comparaison de pointeur
					
					[request setScore:INTERRUPT];
					[request setState:KILLED];
					
					//on retire la requete
					[requests removeObject:request];
					nRequests--;
					
				}
			}
		}
		
		
		//give some informations
		
		if (nSameHash == 0) {
			if(DEBUG)
				NSLog(@"BUG: no hash in requests found");
		} else if (nSameHash == 1) {
			//Kill request
			[self send:[NSString stringWithFormat:@"STOP&asker=%ld&hash=%lx", asker, [aRequest hash]]];
		} else {
			if(DEBUG)
				NSLog(@"WARNING: Transposition == keep request alive");
		}
		
	}
  
	
	[IO_sync unlock];
  
}

/*
 Stop toutes recherches
 */
- (void)aborting
{
  
  abort = YES;
  
	[IO_sync lock];
	
	if(nRequests != 0) {
		
		[self send:[NSString stringWithFormat:@"STOP_ALL&asker=%ld", asker]];
		
		do {
			BC_ZooRequest *request = [requests lastObject];
			
			[request setScore:INTERRUPT];
			
			[request signal:KILLED];
			
			[requests removeLastObject];
			nRequests--;
			
		} while (nRequests != 0);
    
    
	}
	
	[IO_sync unlock];
	
}




/*
 requete ADD
 */
- (void)add:(BC_ZooRequest *)aRequest
{
	
	NSMutableString *req = [NSMutableString stringWithCapacity:200];
	[req appendFormat:@"ADD%@", [aRequest request]];
	[req appendFormat:@"&asker=%ld", asker];
	
	[IO_sync lock];
	
	[requests addObject:aRequest];
	nRequests++;
	
	if([aRequest state] == WORKISWAITING) {
		[self send:req];
		[aRequest setState:SEARCHING];
	} else {
		NSAssert(([aRequest state] == KILLED || [aRequest state] == STOP), @"BUG: requete non KILLED");
		[requests removeObject:aRequest];
		nRequests--;
	}
  
	[IO_sync unlock];
  
}

#pragma mark delegate debug

/*
 DEBUG
 liste les requetes en attente (orphelines)
 */
- (void)listeRequests
{
	[IO_sync lock];
	
	NSLog(@"------------------------------------------------------------------");
	
	for(BC_ZooRequest *aRequest in requests)
		NSLog(@"REQUEST %@", [aRequest request]);
  
	NSLog(@"nRequests == %d", nRequests);
  
	NSLog(@"------------------------------------------------------------------");
  
	[IO_sync unlock];
}

/*
 DEBUG
 redirige NSLog dans un fichier
 */
- (BOOL)redirectNSLog { 
	// Create log file 
	[@"" writeToFile:@"/NSLog.txt" atomically:YES encoding:NSUTF8StringEncoding error:nil];
	id fileHandle = [NSFileHandle fileHandleForWritingAtPath:@"/NSLog.txt"];
	if (!fileHandle)
		return NSLog(@"Opening log failed"), NO; 
  
	// Redirect stderr
	int err = dup2([fileHandle fileDescriptor], STDERR_FILENO);
	if (!err)
		return	NSLog(@"Couldn't redirect stderr"), NO;
	
	return	YES;
} 






#pragma mark delegate method

/*
 ecriture sur outputStream
 */
- (void)send:(NSString *)aString {
  
  
	NSString *stringToSend = [NSString stringWithFormat:@"?action=%@\n", aString];
	NSData *dataToSend = [stringToSend dataUsingEncoding:NSUTF8StringEncoding];
	if (oStream && oStreamCompletedOpen) {
		int remainingToWrite = [dataToSend length];
		void * marker = (void *)[dataToSend bytes];
		while (0 < remainingToWrite) {
			int actuallyWritten = [oStream write:marker maxLength:remainingToWrite];
			remainingToWrite -= actuallyWritten;
			marker += actuallyWritten;
		}
		
    //for debug
    if(DEBUG)
			NSLog(@"send: %@", aString);
	}
  
}


/*
 delagate method
 */
- (void)stream:(NSStream *)stream handleEvent:(NSStreamEvent)eventCode
{
	
	switch (eventCode) {
			
		case NSStreamEventNone:
			
			NSLog(@"NSStreamEventNone");
			break;
			
		case NSStreamEventOpenCompleted:
      
			NSLog(@"NSStreamEventOpenCompleted");
      
			if(stream == iStream)
				iStreamCompletedOpen = YES;
			if(stream == oStream)
				oStreamCompletedOpen = YES;
			
			if(iStreamCompletedOpen && oStreamCompletedOpen) {
				NSLog(@"les streams sont ouvert");
        
				[appController zooDidFinishLaunching];
        
			}
      
			break;
			
		case NSStreamEventErrorOccurred:
			
			NSLog(@"NSStreamEventErrorOccurred");
      
		case NSStreamEventEndEncountered:
      
			NSLog(@"NSStreamEventEndEncountered");			
      
			//un stream est fermé, on ferme les deux.
			[self invalidate];
			[self close];
      
			[appController zooWillClose];
      
			break;
			
		case NSStreamEventHasSpaceAvailable:
			
      //			NSLog(@"NSStreamEventHasSpaceAvailable");
			
			break;
			
		case NSStreamEventHasBytesAvailable:
      
			if(stream == iStream && iStreamCompletedOpen) {
				
				uint8_t oneByte;
				int actuallyRead = 0;
				
				if (nil == _data) {
					_data = [[NSMutableData alloc] initWithCapacity:2048];
				}
				
				actuallyRead = [(NSInputStream *)stream read:&oneByte maxLength:1];
				
				if (actuallyRead == 1) {
					[_data appendBytes:&oneByte length:1];
				}
				
				if (oneByte == '\n') {
					// We've got the carriage return at the end of the echo. Let's set the string.
					NSString *string = [[NSString alloc] initWithData:_data encoding:NSUTF8StringEncoding];
					[self process:string];
					[string release];
					[_data release];
					_data = nil;
				}
				
			}
      
			
			break;
      
		default:
      //			NSLog(@"Not catching event...");
			break;
	}
}

/*
 parse et interprete les reponses du Serveur
 */
- (void)process:(NSString *)aString
{
  
	
	//verification que la connection est tjrs valide
	if(observerConnectTimer && [observerConnectTimer isValid]) {
		NSDate *newFireDate = [NSDate dateWithTimeIntervalSinceNow:30.0]; //30 secondes
		[observerConnectTimer setFireDate:newFireDate];
	}
	
	if(DEBUG)
		NSLog(@"received: %@", aString);
  
	if ([aString hasPrefix:@"STOP_ALL : OK"]) {
		
	} else if ([aString hasPrefix:@"STOP"]) {
		
	} else if ([aString hasPrefix:@"KEEP"]) {
		
	} else if ([aString hasPrefix:@"ADD"]) {
		
	} else if ([aString hasPrefix:@"INCHARGE"]) {
    
	} else if ([aString hasPrefix:@"ERROR_TIMED_OUT"]) {
		
    
		[IO_sync lock];
		
		NSLog(@"ERROR TIMED OUT: %@", aString);
    
		NSArray *components = [aString componentsSeparatedByString:@" "];
    
		//recuperation des infos
		NSUInteger h = 0;
		for(NSString *component in components)
			if([component hasPrefix:@"hash="]) {
				h = [BC_Utils stringToHexa:[component substringFromIndex:5]];
				break;
			}
		
    
		//retrouve la ("une des") requete(s) et la relance
		for(BC_ZooRequest *aRequest in requests) {
      
			if([aRequest state] == SEARCHING && [aRequest hash] == h) {
				
				NSMutableString *req = [NSMutableString stringWithCapacity:200];
				[req appendFormat:@"ADD%@", [aRequest request]];
				[req appendFormat:@"&asker=%ld", asker];
				
				[self send:req];
				break;
				
			}
			
		}
		
		[IO_sync unlock];
		
	} else if ([aString hasPrefix:@"ERROR_HASH_SHOULD_BE_UNIQUE"]) {
		
		
		[IO_sync lock];
		
		NSLog(@"ERROR HASH SHOULD BE UNIQUE: %@", aString);
    
		[IO_sync unlock];
		
	} else if ([aString hasPrefix:@"CALCULATED"]) {
		
		[IO_sync lock];
		
    //		NSLog(@"CALCULATED: %@", aString);
		
		
		NSArray *components = [aString componentsSeparatedByString:@" "];
		
		
		NSUInteger h = 0;	//hash
		float score  = UNDEFSCORE;
		float time   = UNDEFTIME;
		NSString *listMoves = nil;
    
		for(NSString *component in components)
			if([component hasPrefix:@"hash="]) {
				h = [BC_Utils stringToHexa:[component substringFromIndex:5]];
			} else if([component hasPrefix:@"score="]) {
				score = [[component substringFromIndex:6] floatValue];
			} else if([component hasPrefix:@"time="]) {
				time = [[component substringFromIndex:5] floatValue];
			} else if([component hasPrefix:@"moves="]) {
				listMoves = [component substringFromIndex:6];
			}
		
		
		//Attention: requests peut contenir des requetes identiques (Transposition)
		//bien veiller a leur suppression
    
		for(int iRequest = nRequests-1; iRequest >=0; iRequest--) {
			
			BC_ZooRequest *request = [requests objectAtIndex:iRequest];
      
			if([request state] == SEARCHING && [request hash] == h) {
        
				//update info					
				[request setScore:score];
				[request setTime:time];
				[request setListMoves:listMoves];
        
				
				[request signal:TERMINATED];
        
				[requests removeObjectAtIndex:iRequest];
				nRequests--;
        
			}
			
		}
		
    
		[IO_sync unlock];
		
	}// else {
  //		
  //		NSLog(@"ERROR: %@", aString);
  //		
  //	}
  
}


#pragma mark Solver

- (void)startScript:(NSURL *)url
{
  
  [self newTest];
  
  [appController startAnimation];
  
    
  [NSThread detachNewThreadSelector:@selector(solver:) toTarget:self withObject:url];
  
}

- (void)solver:(NSURL *)input
{
  
  NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init]; //top level pool
  
  NSDate *startdate = [NSDate date];
  
  NSString *content = [NSString stringWithContentsOfURL:input encoding:NSUTF8StringEncoding error:NULL];
  NSArray *components = [content componentsSeparatedByString:@"\n"];
  
  NSMutableString *outString = [NSMutableString stringWithCapacity:4096];
  
  unsigned int nPos = 0;
  for(id component in components) {
    
    //traitement des options
    
    if([component hasPrefix:@"% SET OPTION "]) {
      
      NSArray *comps = [component componentsSeparatedByString:@" "];
      
      NSString *value     = nil;
      NSString *forKey    = nil;
      
      for (id comp in comps) {
        if([comp hasPrefix:@"VALUE:"])
          value  = [[comp substringFromIndex:6] stringByTrimmingCharactersInSet:[NSCharacterSet whitespaceAndNewlineCharacterSet]];
        else if ([comp hasPrefix:@"FORKEY:"])
          forKey = [[comp substringFromIndex:7] stringByTrimmingCharactersInSet:[NSCharacterSet whitespaceAndNewlineCharacterSet]];
        
        if(value != nil && forKey != nil)
          break;
      }
      
      if(value != nil && forKey != nil) {
        // nous avons lu une nouvelle option complete dans le script
        NSLog(@"Change Option value: \"%@\" forkey: \"%@\"", value, forKey);
        [options setValue:value forKey:forKey];
        [self changeOptions];
      }
      
      
    } else if([component hasPrefix:@"% START NEW TEST"]) {
      
      // show the timer since begin of test
      [outString appendFormat:@"total time: %@\n\n", [BC_Utils toHMS:[[NSDate date] timeIntervalSinceDate:startdate]]];
      NSLog(@"%@", outString);
      
      // reset the timer
      startdate = [NSDate date];
      nPos = 0;
      
      // tell the zoo and the engines to empty their caches and their hash tables
      [self newTest];
    }
    else if([appController tryParseStringFromScript:component]) {
        
        NSLog(@"lecture de script");
      
      NSMutableString *outResult = [NSMutableString stringWithCapacity:256];
      [outResult appendFormat:@"%@", component];
      [outResult appendString:@"\n"];
      
      abort = NO;
      
      [hashtable clear];
      
      BC_Board *board = [[appController board] copy];
      
      //aspiration search
      BC_ZooRequest *result = [[self driverPVS:board] retain];
      
      if(!abort) {
        nPos++;
        
        [result setListMoves:[self mainLineWithBoard:board score:[result score]]];
        //ecrire dans le fichier
        
        
        [outResult appendFormat:@"%3d | ", nPos];
        [outResult appendFormat:@"%@ | ", [BC_Utils toHMS:[result time]]];
        [outResult appendFormat:@"%+3d@%3ld | ", (int)[result score], [result cut]];
        [outResult appendFormat:@"%@", [result listMoves]];
        [outResult appendString:@"\n"];
        
        //                NSLog(@"%@", outResult);
        
        [outString appendString:outResult];
      }
      
      [board release];
      [result release];
      
      if(abort)
        break;
      
    }
    
    //        [outString appendString:@"\n"];
    
  }
  
  [outString appendFormat:@"total time: %@\n\n", [BC_Utils toHMS:[[NSDate date] timeIntervalSinceDate:startdate]]];
  NSLog(@"%@", outString);
  
  //construction de URL de sortie.
#if (MAC_OS_X_VERSION_MAX_ALLOWED <= MAC_OS_X_VERSION_10_5)
    NSString *output = [[[input path] stringByDeletingPathExtension] stringByAppendingPathExtension:@"output"];
    [outString writeToFile:output atomically:YES encoding:NSUTF8StringEncoding error:NULL];
#else
    NSURL *output = [[input URLByDeletingPathExtension] URLByAppendingPathExtension:@"output"];
    [outString writeToURL:output atomically:YES encoding:NSUTF8StringEncoding error:NULL];
#endif
  
  [appController stopAnimation];

  [pool release];
	  
  
}

- (void)search:(BC_Board *)aBoard
{
	abort = NO;
	
	BC_Board *board = [aBoard copy]; //la copie est retenue
  
	if(![board shouldPass]) {
    
		[appController startAnimation];
    
        [hashtable clear];
		
//		threadMain = [[NSThread alloc] initWithTarget:self selector:@selector(myMainThread:) object:board];		
//		[threadMain start];
		
        [NSThread detachNewThreadSelector:@selector(myMainThread:) toTarget:self withObject:board];
		
	}
	
	[board release];
	
}

- (void)myMainThread:(BC_Board *)aBoard
{
	
	NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init]; //top level pool
  
	[aBoard retain];
  
  
  //aspiration search
  BC_ZooRequest *result = [[self driverPVS:aBoard] retain];	
	
	
	if(!abort) {
		
		//forme une requete "borne standard"
		BC_ZooRequest *ret = [[BC_ZooRequest alloc] initWithPosition:[aBoard descriptionForZoo] 
                                                           alpha:-64 
                                                            beta:+64];
		
		//copie le resultat de la recherche
		[ret setScore:[result score]];
    if ([aBoard n_empties] >= limit_leaf) {
      [ret setListMoves:[self mainLineWithBoard:aBoard score:[result score]]];
    } else {
      [ret setListMoves:[result listMoves]];
    }
		[ret setTime:[result time]];
    
    //        NSMutableString *outResult = [NSMutableString stringWithCapacity:256];
    //        
    //        [outResult appendFormat:@"%@\n", [aBoard descriptionForScript]];
    //        [outResult appendFormat:@"% 1 | "];
    //        [outResult appendFormat:@"%@ | ", [BC_Zoo toHMS:[ret time]]];
    //        [outResult appendFormat:@"%+3d | ", (int)[ret score]];
    //        [outResult appendFormat:@"%@", [ret listMoves]];
    //        
    //        NSLog(@"%@", outResult);
    
    
		[appController addVariationFromRequest:ret];
    
		[ret release];
		
    //		//other variations
    //		NSMutableArray *moves = [NSMutableArray arrayWithCapacity:32];
    //		int nMoves = [aBoard generateAllMoves:moves];
    //		
    //		//excluded bestMove
    //		NSString *bestmove = [[request listMoves] substringToIndex:2];
    //		for(BC_Move *move in moves) {
    //			if ([[move title] isEqualToString:bestmove]) {
    //				[moves removeObject:move];
    //				nMoves--;
    //				break;
    //			}
    //		}
    //		
    //		//creation du splitpoint
    //		BC_SplitPoint *splitpoint = [[[BC_SplitPoint alloc] initWithBoard:aBoard
    //																	moves:moves
    //																	alpha: -64
    //																	 beta: min(64, max(-64, [request score]))
    //																	  cut:100
    //																   parent:nil] retain];
    //		
    //		for(int iMove = 0; iMove < nMoves; iMove++) {
    //			[NSThread detachNewThreadSelector:@selector(MP_PVS:) toTarget:self withObject:splitpoint];
    //		}
    //		
    //		//attente fin de recherche
    //		[splitpoint	wait];
    //		
    //		[splitpoint release];
    
		
	}
  
  
	[result release];
	[aBoard release];
  
	//invalide le timer et stop l'annimation
	[appController stopAnimation];

//    [threadMain autorelease]; //bonne idee?
//	threadMain= nil;

	[pool release];
	
	
}

/* 
 *****************************************************************************************
 *                                                                                       *
 * root_window_policy_for_selectivity() : change la fenetre de recherche à la racine     *
 * dans une passe selective.  La politique que nous suivons ici est d'élargir la fenetre *
 * de plus en plus vers le haut ou vers le bas. On ne peut pas simplement la faire       *
 * coulisser à cause des problèmes d'instabilité bien connus lors des passes sélectives. *
 *                                                                                       *
 *****************************************************************************************
 */
void root_window_policy_for_selectivity(int score, int selectivity, int* lower, int* upper, int* left, int*right)
{
	
	if (score <= *lower) {
		*left = (*left) * 2;
		*lower = score - *left;
	} 
	else 
		
    if (score >= *upper) {
      *right = (*right) * 2;
      *upper = score + *right;
    }
	
	*lower -= (1 - (*lower)&1);
	*upper += (1 - (*upper)&1);
	
	*lower = max(-64, min(63,(*lower)));
	*upper = max(-63, min(64,(*upper)));
	
}


/* 
 *****************************************************************************************
 *                                                                                       *
 * root_window_policy_for_non_selective_pass() : change la fenetre de recherche à la     *
 * racine lors de la passe finale non selective. Ici nous choisissons de faire coulisser *
 * la fenetre vers le haut ou vers le bas, selon la valeur du dernier score retourné.    *
 * La fenetre que nous faisons coulisser est de largeur 2 dans cette implementation.     *
 *                                                                                       *
 *****************************************************************************************
 */
void root_window_policy_for_non_selective_pass(int score, int* lower, int* upper, int* left, int*right)
{
	
	if (score <= *lower) {
		
		*upper = score + 1;
		*lower = (*upper) - (*left);
		
		// *left += 2; 
		// if ((*left) > 4) *left = 4;
	}
	
	
	if (score >= *upper) {
		
		*lower = score - 1;
		*upper = (*lower) + (*right);
		
		// *right += 2;
		// if ((*right) > 4) *right = 4;
	}
	
	*lower -= (1 - (*lower)&1);
	*upper += (1 - (*upper)&1);
	
	*lower = max(-64, min(63,(*lower)));
	*upper = max(-63, min(64,(*upper)));
	
}




/* 
 *****************************************************************************************
 *                                                                                       *
 * driverPVS() : procedure principale pour résoudre une positionde finale.               *
 * On commence par trouver une estimation rapide en milieu de partie de la position,     *
 * on fait deux passes successives de finale à 84% et 100%.                              *
 *                                                                                       *
 *****************************************************************************************
 */
- (BC_ZooRequest *)driverPVS:(BC_Board *)board
{  
  
  
    NSDate *start = [NSDate date];
  
    limit_leaf = max(26, ([board n_empties] - 6));
  
    //step 1: approximation du score
    int score = 0;
  
    if(!abort) {
        if ([board n_empties] > limit_leaf && ![board shouldPass]) {
            BC_ZooRequest *sort = [self evaluateWithBoard:board
                                                    depth:[board n_empties]-14
                                              selectivity:72
                                                    alpha:-64
                                                     beta:+64
                                               splitpoint:nil];        
      
            if([sort state] == TERMINATED)
                score = [sort score];
        }
    
        if (abs(score) > 48)
            limit_leaf = max(26, ([board n_empties] - 4));
        else if (abs(score) > 24)
            limit_leaf = max(26, ([board n_empties] - 5));
    }
  
    
    NSLog(@"--");
    NSLog(@"%@", board);
  
    int selectivity_levels[10] = { 100, 0 };
  
    if (search_should_use_selectivity) { 
        /*
         selectivity_levels[0] = 84;
         selectivity_levels[1] = 95;
         selectivity_levels[2] = 100;
         */
        selectivity_levels[0] = 84;
        selectivity_levels[1] = 100;
    }
  
    BC_ZooRequest *result = nil;
    
    for (int k = 0; selectivity_levels[k] > 0 ; k++) {
  
        int select = selectivity_levels[k];
    
        //le pivot doit etre pair
        score = score - (score&1);
    
    
        //step 2 : aspiration
        //les bornes impaires
        int lower = score -1;
        int upper = score +1;
    
        //limit
        lower = max(-64, min(63,lower));
        upper = max(-63, min(64,upper));
    
        NSLog(@"window @ %d =  [ %d , %d ]",select, lower, upper);
    
        [result release];
        result = [[self PVS:board
                      alpha:lower
                       beta:upper
                selectivity:select
                     passed:NO
                 splitpoint:nil] retain];
    
        score = [result score];
    
        [result setTime:(float)([[NSDate date] timeIntervalSinceDate:start])];
        NSLog(@"%@ | %+3d @%3d | %@", [BC_Utils toHMS:[result time]], score, select, [result listMoves]);
    
        int left  = 2;
        int right = 2;
    
        while (!abort && !(lower < score && score < upper)) {
      
            if ((score <= lower) && (score <= -64)) break;
            if ((score >= upper) && (score >= +64)) break;
      
            if (select < 100)
                root_window_policy_for_selectivity(score, select, &lower, &upper, &left, &right);
            else
                root_window_policy_for_non_selective_pass(score, &lower, &upper, &left, &right);
      
            NSLog(@"window @ %d =  [ %d , %d ]", select, lower, upper);
      
            [result release];
            result = [[self PVS:board
                          alpha:lower
                           beta:upper
                    selectivity:select
                         passed:NO
                     splitpoint:nil] retain];
      
            score = [result score];
      
            [result setTime:(float)([[NSDate date] timeIntervalSinceDate:start])];
            NSLog(@"%@ | %+3d @%3d | %@", [BC_Utils toHMS:[result time]], score, select, [result listMoves]);
        }
    
        NSMutableString *outResult = [NSMutableString stringWithCapacity:256];
    
        [result setTime:(float)([[NSDate date] timeIntervalSinceDate:start])];
        [outResult appendFormat:@"%@ | ", [BC_Utils toHMS:[result time]]];
        [outResult appendFormat:@"%+3d @%3d | ", score, select];
        [outResult appendFormat:@"%@", [result listMoves]];
    
        NSLog(@"%@", outResult);
      
    }
    
    return [result autorelease];
  
}



- (BC_ZooRequest *)PVS:(BC_Board *)board
                 alpha:(int)alpha
                  beta:(int)beta
           selectivity:(unsigned int)cut
                passed:(BOOL)passed
            splitpoint:(BC_SplitPoint *)sp_Parent
{
  
	
	NSAssert(alpha<beta, @"alpha >= beta");
	
	NSAssert(-64 <= alpha && alpha < 64, @"alpha < -64 || alpha >= 64");
	NSAssert(-64 <  beta  && beta <= 64, @"beta <= -64 || beta  >  64");
  
	//declaration variable retour
	BC_ZooRequest *bestResult = nil;
  
    int lower = alpha;
    int upper = beta;
  
    int hashSquare = NOMOVE;
  
    BC_Hashvalue *hashvalue = [[hashtable getWithBoard:board] retain];
    if (hashvalue != nil) {
    
        if ([hashvalue depth] >= [board n_empties] && [hashvalue selectivity] >= cut ) {
      
            if(upper > [hashvalue upper]) {
        
                upper = [hashvalue upper];
                if(upper <= lower) {
          
                    bestResult = [[BC_ZooRequest alloc] initWithPosition:[board descriptionForZoo] 
                                                         alpha:alpha 
                                                          beta:beta
                                                         depth:[hashvalue depth]
                                                           cut:[hashvalue selectivity]];
          
                    [bestResult setMove:[BC_Move indexToString:[hashvalue move]]];
                    [bestResult setScore:upper];
                    [bestResult setTime:0.0f];
                    [bestResult setListMoves:[BC_Move indexToString:[hashvalue move]]];
            
                    [hashvalue release];
          
                    return [bestResult autorelease];
                }
        
            }
      
            if (lower < [hashvalue lower]) {
        
                lower = [hashvalue lower];
                if(lower >= upper) {
          
                    bestResult = [[BC_ZooRequest alloc] initWithPosition:[board descriptionForZoo] 
                                                         alpha:alpha 
                                                          beta:beta
                                                         depth:[hashvalue depth]
                                                           cut:[hashvalue selectivity]];
          
                    [bestResult setMove:[BC_Move indexToString:[hashvalue move]]];
                    [bestResult setScore:lower];
                    [bestResult setTime:0.0f];
                    [bestResult setListMoves:[BC_Move indexToString:[hashvalue move]]];
            
                    [hashvalue release];

                    return [bestResult autorelease];
                }
            }
        }
    
        hashSquare = [hashvalue move];
    
    }
  
    [hashvalue release];
  
	
	
	BOOL  node_is_a_leaf;
	
	if (search_should_use_variable_leaf_horizon) {
    
        node_is_a_leaf =    ((cut >= 100) && ([board n_empties] < limit_leaf )) ||
                            ((cut <  100) && ([board n_empties] < limit_leaf + 2 ));
    
	} else {
		node_is_a_leaf =    ([board n_empties] < limit_leaf);
	}
	
	
	
	//noeud terminal == evaluation
	if (node_is_a_leaf && ![board shouldPass])
		return [self evaluateWithBoard:board
                             depth:[board n_empties]
                       selectivity:cut
                             alpha:lower
                              beta:upper
                        splitpoint:sp_Parent];
  
	
	
	NSMutableArray *moves = [NSMutableArray arrayWithCapacity:32];
	int nMoves = [board generateAllMoves:moves];
	
	
	if (nMoves == 0) {
		//PASS
		if (passed == YES) {
			
			//fin de partie
			bestResult = [[BC_ZooRequest alloc] initWithPosition:[board descriptionForZoo] 
                                                           alpha:-64 
                                                            beta:+64];
			//recup des resultats
            [bestResult setMove:@"--"];
			[bestResult setScore:[board diff_discs]];
			[bestResult setTime:0.0f];
			[bestResult setListMoves:@"--"];
			
			return [bestResult autorelease];
      
		} else {
      
			[board doPass];
			
			bestResult = [[self PVS:board
                              alpha:-upper
                               beta:-lower
                        selectivity:cut
                             passed:YES
                         splitpoint:sp_Parent] retain];
			
            if(![sp_Parent stop]) {
                //recup des resultats
                [bestResult setMove:@"Ps"];
                [bestResult setScore:-[bestResult score]];
                [bestResult setListMoves:[NSString stringWithFormat:@"%@%@", @"Ps", [bestResult listMoves]]];
            }
			
			[board doPass];
      
		}
    
	} else {
    
    //----------------------------------------------------------------------------------------	
    
		
    int YBWC;  // number of sons to evaluate sequentially before going parallel at this node
		
    YBWC = 1;
    
		
    //tres important d'avoir un excellent coup.
    BC_Move *first = [moves objectAtIndex:0];
    
    if(nMoves > 1) {
      NSString *bestMove = nil; 
      
      if (hashSquare == NOMOVE) {
        
        int midgame_ordering_depth = (search_should_use_accurate_ordering ? ([board n_empties]-15) : ([board n_empties]-16));
        
        BC_ZooRequest *sort = [self evaluateWithBoard:board
                                                depth:midgame_ordering_depth
                                          selectivity:72
                                                alpha:-64
                                                 beta:+64
                                           splitpoint:sp_Parent];
        
        
        if(![sp_Parent stop]) {
          bestMove = [[sort listMoves] substringToIndex:2]; 
          
          // Est-t-on presque sûrement dans un noeud ALL et en fenetre nulle ?
          // Alors on essaye le parallelisme speculatif !
          if (search_should_use_speculative_YBWC && ([sort score] <= alpha - 20.0)  && (alpha >= beta - 2))  {
            // NSLog(@"%@", board);
            // NSLog(@"alpha = %d", alpha);
            // NSLog(@"score = %f", [sort score]);
            YBWC = 0;
          }
          
          // Est-t-on presque sûrement dans un noeud CUT et en fenetre nulle ?
          // Alors on essaye le parallelisme speculatif !
            
          //stéphane es-tu sûr de ton commentaire?
          if (search_should_use_conservative_YBWC && ([sort score] >= beta + 10.0)  && (alpha >= beta - 2))  {
            // NSLog(@"%@", board);
            // NSLog(@"beta = %d", beta);
            // NSLog(@"score = %f", [sort score]);
            YBWC = 2;
          }
          
        }
        
        
        
      } else {
        bestMove = [BC_Move indexToString:hashSquare];
      }
      
      
      if (abort || [sp_Parent stop]) {
        return [bestResult autorelease];
      }
      
      
      //retrouve le coup prometteur
      //BC_Move *first = nil;
      for(BC_Move *move in moves) {
        if ([[move title] isEqualToString:bestMove]) {
          first = move;
          break;
        }
      }
    }
        
    //----------------------------------------------------------------------------------------	
    
    int nbMovesEvaluated = 0;
    
    if (YBWC >= 1) {
      
      // l'algo YWBC necessite d'avoir une evaluation sequentielle du premier fils (au moins)
      
      NSAssert(first != nil, @"first = nil");
      
      [board doMove:first];
      
      bestResult = [[self PVS:board
                        alpha:-upper
                         beta:-lower
                  selectivity:cut
                       passed:NO
                   splitpoint:sp_Parent] retain];
      
      
      if(![sp_Parent stop]) {
        //recup des resultats
        [bestResult setMove:[first title]];
        [bestResult setScore:-[bestResult score]];
        [bestResult setListMoves:[NSString stringWithFormat:@"%@%@", [first title], [bestResult listMoves]]];
        
        if([bestResult score] > lower)
          lower = [bestResult score];
        
      }
      
      nbMovesEvaluated++;
      [board undoMove:first];
      
      [moves removeObject:first];
      nMoves--;
    }
    else 
    {
      // preparation d'une requete bidon pour stocker les resultats du parallelisme
      
      bestResult = [[BC_ZooRequest alloc] initWithPosition:[board descriptionForZoo] 
                                                     alpha:lower 
                                                      beta:upper];
      
      //le bestmove est le 1er de la liste
      [bestResult setMove:[first title]];
      [bestResult setScore:MINSCORE];
      [bestResult setListMoves:[first title]];
      
    }
    
    
    if (!abort && ![sp_Parent stop] && nMoves > 0 && lower < upper ) {
      
      //tri sur la mobilité (gestion des priorités)
      if(nMoves > 1)
        [board sort_fastfirst:moves];
      
      while (!abort && ![sp_Parent stop] && nMoves > 0 && lower < upper) {
        
        //peut on paralleliser?
        if ((nMoves > 1) && 
            (nbMovesEvaluated >= YBWC) &&
            [self splitWithBoard:board
                       listMoves:moves
                           alpha:lower
                            beta:upper
                     selectivity:cut
                      splitpoint:sp_Parent
                          result:bestResult])
        {
          break;
        }
        
        //traitement sequentiel
        
        BC_Move *move = [moves objectAtIndex:0];
        
        [board doMove:move];
        
        BC_ZooRequest *result = [[self PVS:board
                                     alpha:-lower-1
                                      beta:-lower
                               selectivity:cut
                                    passed:NO
                                splitpoint:sp_Parent] retain];
        
        //recup des resultats
        [result setMove:[move title]];
        [result setScore:-[result score]];
        [result setListMoves:[NSString stringWithFormat:@"%@%@", [move title], [result listMoves]]];
        
        if(!abort && ![sp_Parent stop]) {
          
          if(lower < [result score] && [result score] < upper) {
            
            float score = [result score];
              
            [result release];
            result = [[self PVS:board
                          alpha:-upper
                           beta:(cut == 100? -score:-lower)
                    selectivity:cut
                         passed:NO
                     splitpoint:sp_Parent] retain];
            
            
            //recup des resultats
            [result setMove:[move title]];
            [result setScore:-[result score]];
            [result setListMoves:[NSString stringWithFormat:@"%@%@", [move title], [result listMoves]]];
          }
        }
        
          nbMovesEvaluated++;
          [board undoMove:move];
        
          [moves removeObjectAtIndex:0];
          nMoves--;
        
          if (abort || [sp_Parent stop]) {
              [result release];
              break;
          }
        
        //update
        if([result score] > [bestResult score]) {
          
          //ici nous ne mettons a jour que le score
          //c'est un choix
          [bestResult setScore:[result score]];
          
          
          if([bestResult score] > lower) {
            
            //le bestmove et la pv si et seulement si > lower
            [bestResult setMove:[result move]];
            [bestResult setListMoves:[result listMoves]];

            lower = [bestResult score];
          }
        }
        
        [result release];
        
      }
    }
    
  }
  
  
  
  
    if(![sp_Parent stop]) {
        
        //update Hashtable
        [hashtable  updateWithBoard:board
                        selectivity:cut
                              depth:[board n_empties]
                             square:[BC_Move stringToIndex:[bestResult move]]
                              alpha:alpha
                               beta:beta
                              score:[bestResult score]];
    }
  
  
    return [bestResult autorelease];
	
}


- (void)MP_NWS:(BC_SplitPoint *)splitpoint //normalement (id)
{
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init]; //top level pool
	
	NSAssert(splitpoint != nil, @"splitpoint = nil");
	
	BC_Board *board = [[BC_Board alloc] initWithString:[splitpoint descriptionForZoo]];
	BC_Move  *move  = [[splitpoint nextMove] retain];
	
	NSAssert(move != nil, @"WARNING: pas de move");
	
	if(move != nil && ![splitpoint stop]) {
		
		//alpha local 
		NSInteger alphaLocal = [splitpoint alpha];
		
		if(alphaLocal < [splitpoint beta]) {
			
			[board doMove:move];
			
			BC_ZooRequest *result = [[self PVS:board 
                                         alpha:-alphaLocal-1
                                          beta:-alphaLocal
                                   selectivity:[splitpoint cut]
                                        passed:NO
                                    splitpoint:splitpoint] retain];
			
			
			//recup des resultats
            [result setMove:[move title]];
			[result setScore:-[result score]];
			[result setListMoves:[NSString stringWithFormat:@"%@%@", [move title], [result listMoves]]];
			
            if (![splitpoint stop] && 
                alphaLocal < [result score] && [result score] < [splitpoint beta]) {
				
				//modification des bornes la requete
				//WARNING: [splitpoint alpha] updaté par un autre thread peut etre superieur
				alphaLocal = max([result score], [splitpoint alpha]);
				
				if(alphaLocal < [splitpoint beta]) {
					
					//libere la requete NWS
					[result release];
                    
					result = [[self PVS:board
                                  alpha:-[splitpoint beta]
                                   beta:([splitpoint cut] == 100? -alphaLocal:-[splitpoint alpha])
                            selectivity:[splitpoint cut]
                                 passed:NO
                             splitpoint:splitpoint] retain];
          
					
					//recup des resultats
                    [result setMove:[move title]];
					[result setScore:-[result score]];
					[result setListMoves:[NSString stringWithFormat:@"%@%@", [move title], [result listMoves]]];
				}
				
            }
			
            [board undoMove:move];
			
      
            @synchronized(splitpoint) {
            
                if(![splitpoint stop]) {
                  
                  //update du splitpoint
                  if (([result score]) > [splitpoint bestscore]) {
                    
                    //mise a jour uniquement du score
                    [splitpoint setBestscore:[result score]];
                    
                    if([splitpoint bestscore]>[splitpoint alpha]) {
                    
                      //mise a jour du bestMove et de la PV si et seulement si > alpha
                      [splitpoint setBestMove:[result move]];
                      [splitpoint setBestPV:[result listMoves]];
                    
                        //update alpha
                      [splitpoint setAlpha:[splitpoint bestscore]];
                      
                      if ([splitpoint alpha] >= [splitpoint beta]) {
                        [splitpoint should_stop];
                      }
                    }
                  }
                }
            }
			
			[result release];
		}
		
	}
	
	[move release];
	[board release];
	
	[splitpoint signal];
	
	[pool release];
}

- (BC_ZooRequest *)evaluateWithBoard:(BC_Board *)board
                               depth:(unsigned int)aDepth
                         selectivity:(unsigned int)aCut
                               alpha:(int)lower
                                beta:(int)upper
                          splitpoint:(BC_SplitPoint *)sp
{
  
  BC_ZooRequest *request = [[BC_ZooRequest alloc] initWithPosition:[board descriptionForZoo] 
                                                             alpha:lower 
                                                              beta:upper		
                                                             depth:aDepth
                                                               cut:aCut];
  
  //lance la requete
  if(!abort && (sp == nil || [sp add:request])) {
    
    [self add:request];
    
    [request wait];
    
    if ([request state] == STOP) {
      [self stopRequest:request];
    }
    
    [sp remove:request];
    
  }
  
  return [request autorelease];
  
}

- (BOOL)splitWithBoard:(BC_Board *)board
             listMoves:(NSMutableArray *)moves
                 alpha:(int)lower
                  beta:(int)upper
           selectivity:(unsigned int)cut
            splitpoint:(BC_SplitPoint *)sp_Parent
                result:(BC_ZooRequest *)result

{
  [createThreadLock lock];
  if (nThreads < MAX_THREADS) {
    //traitement paralelle
    
    const int nMoves = [moves count];
    
    nThreads += nMoves;
    [createThreadLock unlock];
    
    //creation du splitpoint
    BC_SplitPoint *splitpoint = [[BC_SplitPoint alloc] initWithBoard:board
                                                               moves:moves
                                                               alpha:lower
                                                                beta:upper
                                                                 cut:cut
                                                              parent:sp_Parent];
    
    if(!abort && (sp_Parent == nil || [sp_Parent add:splitpoint])) {
      
      
      //MacOs >= 10.5)
      NSThread *threads[nMoves];
      for(int iMove = 0; iMove < nMoves; iMove++) {
        threads[iMove] = [[NSThread alloc] initWithTarget:self
                                                 selector:@selector(MP_NWS:)
                                                   object:splitpoint];
        [threads[iMove] start];			
      }
      
      
      //attente fin de recherche
      [splitpoint wait];
      
      
      //liberation des threads
      for(int iMove = 0; iMove < nMoves; iMove++) {
        [threads[iMove] release];
      }
      
      
      //update requete si necessaire
      if(![sp_Parent stop] && [splitpoint bestscore] > [result score]) {
        [result setMove:[splitpoint bestMove]];
        [result setScore:[splitpoint bestscore]];
        [result setListMoves:[splitpoint bestPV]];
      }
      
      [sp_Parent remove:splitpoint];
    }
    
    
    [splitpoint release];
    
    [createThreadLock lock];
    nThreads -= nMoves;
    [createThreadLock unlock];
    
    //sortie de la boucle
    return YES;
  }
  
  [createThreadLock unlock];
  return NO;
  
}

/*
 verifie la pv
 */
- (NSString *)mainLineWithBoard:(BC_Board *)board
                          score:(int)value
{
  
  if ([board n_empties] < limit_leaf && ![board shouldPass]) {
    
    NSLog(@"Appel du zoo à %d empties pour vérifier la PV...", [board n_empties]);
    
    BC_ZooRequest *request = [self evaluateWithBoard:board
                                               depth:[board n_empties]
                                         selectivity:100
                                               alpha:max(-64, min(63,value-1))
                                                beta:max(-63, min(64,value+1))
                                          splitpoint:nil];
    
    if ([request score] != value) {
      NSLog(@"ERROR : Wrong PV");
    }
    
    return [request listMoves];
  }
  
  
  NSString *ret = nil;
  
  BC_Hashvalue *hashvalue = [[hashtable getWithBoard:board] retain];
  if (hashvalue != nil) {
    
    int hashSquare = [hashvalue move];
    
    if (hashSquare == PASS) {
      [board doPass];
      ret = [NSString stringWithFormat:@"Ps%@", [self mainLineWithBoard:board score:-value]];
      [board doPass];
    } else {
      
      BC_Move *move = [[BC_Move alloc] initWithLocation:hashSquare];
      int flips = [board generateMove:move];
      
      if(flips) {
        [board doMove:move];
        ret = [NSString stringWithFormat:@"%@%@", [BC_Move indexToString:hashSquare], [self mainLineWithBoard:board score:-value]];
        [board undoMove:move];
      }
        
        [move release];
    }
  }
  
  [hashvalue release];
  
  return ret;
  
  
}


@end
